package Acwing.搜索与图论;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @Title: walkTheMaze
 * @Author 贾金博
 * @Package Acwing.搜索与图论
 * @Date 2025/4/11 下午6:32
 * @description: bfs最少问题 经典应用 走迷宫
 */
public class walkTheMaze {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] a = new int[n + 10][m + 10];
        boolean[][] st = new boolean[n + 10][m + 10];
        int[] X = {0, 1, 0, -1};
        int[] Y = {1, 0, -1, 0};

        for(int i = 1; i <= n; i ++ ) {
            for(int j = 1; j <= m; j ++ ) {
                a[i][j] = sc.nextInt();
            }
        }

        int[][] ret = new int[n + 10][m + 10];
        for(int i = 1; i <= n; i ++ ) {
            for(int j = 1; j <= m; j ++ ) {
                ret[i][j] = Integer.MAX_VALUE; // 初始化为最大的数
            }
        }
        ret[1][1] = 0;
        Queue<pos> q = new LinkedList<>();
        q.add(new pos(1, 1));
        st[1][1] = true;

        while(!q.isEmpty()) {
            pos t = q.poll();
            for(int i = 0; i < 4; i++) {

                int newX = t.x + X[i];
                int newY = t.y + Y[i];

                // 注意这里要去检查坐标是否是合法的
                if(newX >= 1 && newX <= n && newY >= 1 && newY <= m && !st[newX][newY] && a[newX][newY] == 0) {
                    st[newX][newY] = true;
                    ret[newX][newY] = ret[t.x][t.y] + 1;
                    // 把这个合法地放入到 队列里面
                    q.add(new pos(newX, newY));
                }

            }
        }
        System.out.println(ret[n][m]);

    }
}

class pos {

    int x, y;

    // 构造方法不带返回值类型
    public pos(int x, int y) {
        this.x = x;
        this.y = y;
    }

}
